#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef char ElementType;
typedef struct _queue{
    ElementType Elm;
    struct _queue *Next;
    struct _queue *Tail;
} queue;

queue *queueInit();
bool  queueEmpty(queue*);
bool  enQueue(queue*,ElementType);
ElementType deQueue(queue*);

char* convert(char* s, int numRows) {
    if( numRows==1 )
        return s;
    queue *qArr[numRows];
    for(int i=0; i<numRows; i++)
        qArr[i]=queueInit();
    int bucket=0,idx=0,direct=1;
    while( s[idx] != '\0' ){
        if( bucket== 0 )
            direct=1;
        if( bucket== numRows-1 )
            direct=-1;
        enQueue( qArr[ bucket ], s[idx] );
        bucket+=direct;
        idx++;
    }
    char *ans=malloc(sizeof(char)*(idx+1));
    idx=0;
    for(int i=0;i<numRows;i++){
        while( !queueEmpty(qArr[i]) ){
            ans[idx++]=deQueue(qArr[i]);
        }
    }
    ans[idx]='\0';
    return ans;
}
queue *queueInit(){
    queue* q=malloc(sizeof(queue));
    q->Next=NULL;
    q->Tail=q;
    return q;
}
bool  queueEmpty(queue* q){
    return (q->Next==NULL);
}
bool  enQueue(queue* q,ElementType elm){
    queue *n=malloc(sizeof(queue));
    if( !n )return false;
    n->Elm=elm;
    n->Next=NULL;
    q->Tail->Next=n;
    q->Tail=n;
    return true;
}
ElementType deQueue(queue* q){
    queue *tmp=q->Next;
    ElementType r=tmp->Elm;
    q->Next=tmp->Next;
    free(tmp);
    if( !q->Next )
        q->Tail=q;
    return r;
}

int main(){
    char *s=convert("PAYPALISHIRING",4);
    printf("%s\n",s);
    return 0;
}
